package simple;

/**
 * {@link
 * https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=188&&tqId=38576&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking}
 *
 * 判断给定的链表中是否有环。如果有环则返回true，否则返回false。
 *
 * 数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中任意节点的值满足 |val| <= 100000∣val∣<=100000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * 输入分为2部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
 *
 * 例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
 *
 * @author WangZhiJian
 * @since 2022/1/4
 */
public class 判断链表中是否有环 {

    /**
     * 快慢指针解法, 初始化慢指针等于head,快指针指向head的后一位
     * 慢指针一次走一步
     * 快指针一次走二步
     * 二者一直不为null则一直往后走
     * 如果二者相等则存在回环
     * 否则不存在
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head) {
        ListNode quick = head == null ? null : head.next;
        ListNode slow = head;

        while(quick != null && slow != null){
            if(quick == slow)
                return true;
            slow = slow.next;
            quick = quick.next == null ? null : quick.next.next;
        }
        return false;
    }



    static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }
}
